翻訳と辞書
Words near each other
・ SNCF BB 1420
・ SNCF BB 200
・ SNCF BB 20011 and 20012
・ SNCF Class 141R
・ SNCF class 141TB
・ SNCF Class 241P
・ SNCF Class A1AA1A 68000
・ SNCF Class B 81500
・ SNCF Class B 82500
・ SNCF Class BB 10003
・ SNCF Class BB 12000
・ SNCF Class BB 15000
・ Snaring Mountain
・ Snaring River
・ Snark
Snark (graph theory)
・ Snark (Lewis Carroll)
・ SNARK (theorem prover)
・ Snark Missile Launch Complex
・ Snark sailboat
・ Snarki
・ Snarkitecture
・ Snarky Puppy
・ Snarl
・ Snarl (disambiguation)
・ Snarl (software)
・ Snarl (Transformers)
・ Snarler
・ Snarleyow
・ Snarling at Strangers


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Snark (graph theory) : ウィキペディア英語版
Snark (graph theory)

In the mathematical field of graph theory, a snark is a connected, bridgeless cubic graph with chromatic index equal to 4. In other words, it is a graph in which every vertex has three neighbors, and the edges cannot be colored by only three colors without two edges of the same color meeting at a point. (By Vizing's theorem, the chromatic index of a cubic graph is 3 or 4.) In order to avoid trivial cases, snarks are often restricted to have girth at least 5.
Writing in The Electronic Journal of Combinatorics, Miroslav Chladný states that
==History==
P. G. Tait initiated the study of snarks in 1880, when he proved that the four color theorem is equivalent to the statement that no snark is planar. The first known snark was the Petersen graph, discovered in 1898. In 1946, Croatian mathematician Danilo Blanuša discovered two more snarks, both on 18 vertices, now named the Blanuša snarks. The fourth known snark was found two years later by Bill Tutte, under the pseudonym Blanche Descartes, and was a graph of order 210.〔Blanche Descartes, Network-colourings, The Mathematical Gazette (London) 32, 67-69, 1948.〕〔Martin Gardner, The Last Recreations: Hydras, Eggs, and Other Mathematical Mystifications, Springer, 2007, ISBN 0-387-25827-2, ISBN 978-0-387-25827-0〕 In 1973, George Szekeres found the fifth known snark — the Szekeres snark. In 1975, Rufus Isaacs generalized Blanuša's method to construct two infinite families of snarks: the flower snark and the BDS or Blanuša–Descartes–Szekeres snark, a family that includes the two Blanuša snarks, the Descartes snark and the Szekeres snark. Isaacs also discovered a 30-vertices snark that does not belong to the BDS family and that is not a flower snark: the double-star snark.
Snarks were so named by the American mathematician Martin Gardner in 1976, after the mysterious and elusive object of the poem ''The Hunting of the Snark'' by Lewis Carroll.

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Snark (graph theory)」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.